// 排序

let arr = [10,3,4,5,2,1,2,3,4,1,2,12,43,56,22,1,9,8]

//sortArr(arr)
//quicksort(arr)

console.log(quickSort1(arr))

// 冒泡排序
function sortArr(arr){
    for(let i in arr){
        for(let j in arr){
            if(arr[i] < arr[j]){
                let big = arr[i]
                let small = arr[j]
                arr[i] = small
                arr[j] = big
            }
        }
    }
    console.log(arr)
}

// 快速排序
// 算法参考某个元素值，将小于它的值，放到左数组中，大于它的值的元素就放到右数组中，然后递归
function quicksort(arr) {
    if(arr.length < 2){
        return arr
    }

    let refer = arr[0]
    let leftArr = []
    let rightArr = []

    for(let i in arr){
        if(arr[i] < refer){
            leftArr.push(arr[i])
        }else{
            rightArr.push(arr[i])
        }
    }

    // console.log(leftArr)
    // console.log(rightArr)
    // quicksort(leftArr)
    let result = [].concat(quicksort(leftArr), quicksort(rightArr))
    console.log(result)
}

function quickSort1(arr) {

    if(arr.length<=1) {
        return arr;
    }

    let leftArr = [];
    let rightArr = [];
    let q = arr[0];
    for(let i = 1,l=arr.length; i<l; i++) {
        if(arr[i]>q) {
            rightArr.push(arr[i]);
        }else{
            leftArr.push(arr[i]);
        }
    }

    return [].concat(quickSort1(leftArr),[q],quickSort1(rightArr));
}